﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
void test_list1() {
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	list<int>::iterator it = lt.begin();
	while (it != lt.end()) {
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : lt) {
		cout << e << " ";
	}
	cout << endl;

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	if (pos != lt.end()) {
		lt.insert(pos, 30);
	}
	for (auto e : lt) {
		cout << e << " ";
	}
	cout << endl;
}
void test_list2()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(5);
	lt.push_back(3);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.sort();
	//迭代器功能分类
	//1.单向 ++
	//2.双向 ++ --
	//3.随机 ++ -- + -
	//sort(lt.begin(), lt.end());
	for (auto e : lt) {
		cout << e << " ";
	}
	cout << endl;
	lt.unique();

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//lt.remove(30);
	lt.remove(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}
void test_op()
{
	srand(time(0));
	const int N = 1000000;

	vector<int> v1;
	v1.reserve(N);
	vector<int> v2;
	v2.reserve(N);
	deque<int> dq1;
	deque<int> dq2;
	list<int> lt1;
	//list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		v2.push_back(e);
		//lt2.push_back(e);
		dq1.push_back(e);
		dq2.push_back(e);
	}
	int begin1 = clock();
	for (auto e : dq1) {
		v1.push_back(e);
	}
	sort(v1.begin(), v1.end());
	size_t i = 0;
	for (auto& e : dq1) {
		e = v1[i++];
	}
	// lt2
	//lt2.assign(v.begin(), v.end());

	int end1 = clock();

	int begin4 = clock();
	sort(v2.begin(), v2.end());
	int end4 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	int begin3 = clock();
	sort(dq2.begin(), dq2.end());
	int end3 = clock();

	//printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
	//printf("list sort:%d\n", end2 - begin2);

	printf("vector sort:%d\n", end4 - begin4);
	printf("deque copy vector copy deque sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
	printf("deque sort:%d\n", end3 - begin3);
}
int main() {
	test_op();
	return 0;
}